import java.util.Arrays;

public class Solution1300 {
    public int findBestValue(int[] arr, int target) {
        Arrays.sort(arr);
        int[] sum=new int[arr.length+1];
        sum[0]=0;
        for (int i=1;i<=arr.length;i++){
            sum[i]=sum[i-1]+arr[i-1];
        }
        int l=0,r=arr.length-1;
        int ans=-1;
        while (l<=r){
            int mid=(l+r)/2;
            int t=sum[mid]+arr[mid]*(arr.length-mid);
            if (t>=target){
                ans=mid;
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        int left,right;
        if (ans==-1){
            return arr[arr.length-1];
        }else if (ans==0){
            left=0;
            right=arr[0];
        }else{
            left=arr[ans-1];
            right=arr[ans];
        }
        int m=-1,pos=-1;
        while (left<=right){
            int mid=(left+right)/2;
            int t=sum[ans]+mid*(arr.length-ans);
            if (Math.abs(m-target)>Math.abs(t-target)){
                m=t;
                pos=mid;
            }
            if (t<=target){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return pos;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1300().findBestValue(new int[]{1547,83230,57084,93444,70879},71237));
    }
}
